package com.zyk.grate_offer.class06;

/**
 * @author zhangsan
 * @date 2021/5/10 20:11
 */
public class Code01_MaximumXorSumInSubArray {

    // 暴力解 O(N^2)
    public static int maxXorSubarray1(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int max = nums[0], N = nums.length;
        for (int i = 1; i < N; i++) {
            int pre = nums[i];
            max = Math.max(max, pre);
            for (int j = i - 1; j >= 0; j--) {
                max = Math.max(max, (pre ^= nums[j]));
            }
        }
        return max;
    }

    // O(N^2)
    public static int maxXorSubarray2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        // 准备一个前缀异或和数组eor
        // eor[i] = arr[0...i]的异或结果
        int[] eor = new int[arr.length];
        eor[0] = arr[0];
        // 生成eor数组，eor[i]代表arr[0..i]的异或和
        for (int i = 1; i < arr.length; i++) {
            eor[i] = eor[i - 1] ^ arr[i];
        }
        int max = Integer.MIN_VALUE;
        for (int j = 0; j < arr.length; j++) {
            for (int i = 0; i <= j; i++) { // 依次尝试arr[0..j]、arr[1..j]..arr[i..j]..arr[j..j]
                max = Math.max(max, i == 0 ? eor[j] : eor[j] ^ eor[i - 1]);
            }
        }
        return max;
    }

    public static int maxXorSubarray3(int[] arr) {
        if (arr == null || arr.length == 0) return 0;
        TrieNum tree = new TrieNum();
        tree.add(0);    // 把 0000~000 初始化好
        int eor = 0, max = Integer.MIN_VALUE;    // 异或和
        for (int num : arr) {
            eor ^= num;
            max = Math.max(max, tree.maxXor(eor));
            tree.add(eor);
        }
        return max;
    }

    public static class TrieNum {

        public static Node head;

        public TrieNum() {
            head = new Node();
        }

        public void add(int num) {  // 从32位高往低建树
            Node cur = head;
            int path;
            for (int i = 31; i >= 0; i--) {
                path = (num >> i) & 1;
                if (cur.next[path] == null)
                    cur.next[path] = new Node();
                cur = cur.next[path];
            }
        }

        public int maxXor(int sum) {
            Node cur = head;
            int path = (sum >> 31) & 1,         // path = sum这一位的值.
                    best = cur.next[path] == null ? (path ^ 1) : path,  // 是实际上走的最优的路
                    res = (path ^ best) << 31;
            cur = cur.next[best];
            for (int i = 30; i >= 0; i--) {     // 从高位往低位走
                path = (sum >> i) & 1;      // path是这一位的值
                best = (path ^ 1);     // 期待的路, 如果是符号位想要0, 否则想要1
                best = cur.next[best] == null ? (best ^ 1) : best;  // 实际的路, 因为这个路肯能为空
                res |= (path ^ best) << i;  // ??? 这里得算一下
                cur = cur.next[best];
            }
            return res;
        }

        public int maxXor2(int sum) {
            Node cur = head;
            int path, best, res = 0;
            for (int i = 31; i >= 0; i--) {     // 从高位往低位走
                path = (sum >> i) & 1;      // path是这一位的值
                best = i == 31 ? path : (path ^ 1);     // 期待的路, 如果是符号位想要0, 否则想要1
                best = cur.next[best] == null ? (best ^ 1) : best;  // 实际的路, 因为这个路肯能为空
                res |= (path ^ best) << i;  // ??? 这里得算一下
                cur = cur.next[best];
            }
            return res;
        }

        public static class Node {
            Node[] next = new Node[2];
        }
    }

    // for test
    public static void main(String[] args) {
        /*TrieNum tree = new TrieNum();
        tree.add(41);
        tree.add(1);
        tree.add(2);
        System.out.println(tree.maxXor(Integer.MIN_VALUE));*/

        int testTime = 500000;
        int maxSize = 30;
        int maxValue = 50;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr = generateRandomArray(maxSize, maxValue);
            int comp = maxXorSubarray1(arr);
            int res = maxXorSubarray2(arr);
            int res2 = maxXorSubarray3(arr);
            if (res != comp || res != res2) {
                succeed = false;
                printArray(arr);
                System.out.println(res);
                System.out.println(res2);
                System.out.println(comp);
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}
